package N皇后问题;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zhengTao
 * @version 1.0
 * @description: N 皇后   困难， 先套用回溯模板
 * @date 2022/11/19 16:45
 */
public class Demo51 {
    List<List<String>> res=new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
           char[][] qiPan=new char[n][n];
           //给棋盘赋初始值
           for (int i = 0; i < qiPan.length; i++) {
               char[] chars = qiPan[i];
               Arrays.fill(chars,'.');
           }
           backTrack(qiPan,0);
           return res;
    }

    private void backTrack(char[][] qiPan, int row) {
        //到达n证明棋盘满足条件，直接返回 (0行开始，row==n,证明n-1满足条件)
        if(row==qiPan.length){
            //棋盘转成list的字符串
            List<String> temp=Array2List(qiPan);
            res.add(temp);
            return;
        }
        //开始遍历,i表示每一列，row表示每一行
        for (int i = 0; i < qiPan.length; i++) {
            if(validQiPan(qiPan,i,row)){
                qiPan[row][i]='Q';
                backTrack(qiPan,row+1);
                //回溯
                qiPan[row][i]='.';
            }
        }
    }

    private boolean validQiPan(char[][] qiPan, int col, int row) {
        //校验列
        for (int i = 0; i < row; i++) {
            if(qiPan[i][col]=='Q'){
                return false;
            }
        }
        //校验45°角  假设棋盘为3  当前元素位置是(2,1) 上一个位置为(1,0)
        for (int j = col-1,i=row-1; j>=0&&i>=0 ; j--,i--) {
            if(qiPan[i][j]=='Q'){
                return false;
            }
        }
        //校验125°角  假设棋盘为3  当前元素位置是(1,1), 上一个位置为(0,2)
        for (int j = col+1,i=row-1; j<= qiPan.length-1&&i>=0 ; j++,i--) {
            if(qiPan[i][j]=='Q'){
                return false;
            }
        }
        return true;
    }

    private List<String> Array2List(char[][] qiPan) {
        List<String> res=new ArrayList<>();
        for (int i = 0; i < qiPan.length; i++) {
            String str=new String(qiPan[i]);
            res.add(str);
        }
        return res;
    }
}
